//练习：九宫格的连通性证明问题
#include<stdio.h>
#include<malloc.h>
#include<string.h>

//3.1 图结构体实现
#define MAXSIZE 3
#define ZERO 0
#define TRUE 1                              //定义符号常量“真”
#define FALSE 0                             //定义符号常量“假”
typedef int NODE[MAXSIZE][MAXSIZE];
typedef int STATUS;
double count = 0.0;

typedef struct NEIGHBORNODE          //节点类型
{
    NODE node;                       //节点
    struct NEIGHBORNODE* next;       //领进节点
}NEIGHBORNODE, * NEIGHBOR;             //相邻节点类型【*NEIGHBOR和下文中*PATH均为指向NEIGHBORNODE的指针】

typedef struct NEIGHBORNODE* PATH;   //路径类型

//3.2.2 赋值两个九宫格
void Set(NODE node1, NODE node2)
{
    int i, j;
    for (i = 0; i < MAXSIZE; i++)
    {
        for (j = 0; j < MAXSIZE; j++)
        {
            node1[i][j] = node2[i][j];
        }
    }
}

//3.7.1 判断两个九宫格是否相同
STATUS equal(NODE node1, NODE node2)
{
    int i, j;
    STATUS flag = TRUE;
    for (i = 0; i < MAXSIZE; i++)
    {
        for (j = 0; j < MAXSIZE; j++)
        {
            if (node1[i][j] != node2[i][j])
            {
                flag = FALSE;
                return 1;
                break;
            }
        }
        if (flag == FALSE)   break;
    }
    return 0;
}

//3.7.2 显示九宫格
void PriNode(NODE node)
{
    int i, j;
    for (i = 0; i < MAXSIZE; i++)
    {
        for (j = 0; j < MAXSIZE; j++)  printf("%5d", node[i][j]);
        printf("\n");
    }
    printf("****************\n");
}

//3.2.3 相邻节点关系的构建
NEIGHBOR Add_A_Adjacents(NEIGHBOR br, NODE node)        //Add_A_Adjacents把一个节点加入到相邻节点群中
{
    NEIGHBOR b, pb;                                  //相邻节点
    b = (NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE)); //动态开辟一个相邻节点
    Set(b->node, node);             //【下面两行是类型为str时的情况，其他类比】
    b->next = NULL;
    if (br == NULL)                                    //没有相邻节点的情况
    {
        br = b;                                       //node就是第一个邻居
    }
    else                                            //有相邻节点的情况
    {
        pb = br;                                      //node就是最后一个相邻节点【值在b中，头插入】
        while (pb->next)   pb = pb->next;
        pb->next = b;
    }
    return br;                                      //返回相邻节点【指针】
}

//3.2.6 清除相邻节点和图
NEIGHBOR ClearNeighbors(NEIGHBOR br)  //回收相邻节点空间
{
    NEIGHBOR br1 = br;                 //临时相邻变量
    while (br)                        //【遍历相邻节点】
    {
        br1 = br;
        br = br->next;                //【挨个变量赋给临时指针】
        free(br1);                  //回收单元
        return br;
    }
    return br;                      //返回NULL
}

//3.4.1 判断节点是否在路径中
STATUS IsInPath(NODE node, PATH path)                      //判断节点是否在路径中并返回真或假
{
    PATH p = path;
    STATUS flag = FALSE;                                    //节点是否在路径中的标识
    while (p)
    {
        if (equal(node, p->node) == 0)                       //node在路径中
        {
            flag = TRUE;
            break;
        }
        else                                              //node不在路径中
        {
            p = p->next;
        }
    }
    return flag;                                          //返回真/假
}

//3.6.1 判断节点的存在性
STATUS IsInAdjacents(NODE node, NEIGHBOR adjacents)   //判断节点是否在节点集合中
{
    PATH path = (PATH)adjacents;                       //节点集合与路径节点存储结构相同
    return IsInPath(node, path);                      //节点是否在路径中，复用函数IsInPath
}

//3.6.7 合并节点集
NEIGHBOR UnionAdjacents(NEIGHBOR adjacents, NEIGHBOR alladjacents)     //节点集合合并【形成总节点集合】
{
    while (adjacents)                                                  //所有节点（节点集合不为空）
    {
        alladjacents = Add_A_Adjacents(alladjacents, adjacents->node);   //加入节点
        adjacents = adjacents->next;                                    //下一个节点
        count++;
    }
    return alladjacents;                                              //合并后集合
}

//3.6.8 相差节点集
NEIGHBOR DiffAdjancents(NEIGHBOR adjacents, NEIGHBOR alladjacents)     //节点集合合并【将不在总结点集合中的点加入差节点集合】
{
    NEIGHBOR minusadjacents = NULL;                                     //新节点集合【差节点集合】
    while (adjacents)                                                  //所有节点
    {
        if (IsInAdjacents(adjacents->node, alladjacents) == FALSE)
        {
            minusadjacents = Add_A_Adjacents(minusadjacents, adjacents->node);
        }
        adjacents = adjacents->next;                                    //下一个节点
    }
    return minusadjacents;                                            //节点集合的差集
}

//3.7.3 九宫格的空格交换
STATUS Locate(NODE node, int* hori, int* vert, int zero)
{
    int i, j;
    STATUS flag = FALSE;
    for (i = 0; i < MAXSIZE; i++)
    {
        for (j = 0; j < MAXSIZE; j++)
        {
            if (node[i][j] == zero)
            {
                *hori = i;
                *vert = j;
                flag = TRUE;
                break;
            }
        }
        if (flag == TRUE)   break;
    }
    return flag;
}

void Exchange(NODE node, int hori1, int vert1, int hori2, int vert2)
{
    int tempnode;
    tempnode = node[hori1][vert1];
    node[hori1][vert1] = node[hori2][vert2];
    node[hori2][vert2] = tempnode;
}

//3.7.4 相邻节点集合的生成
NEIGHBOR ExpandNodes(NODE node, int zero){
    NEIGHBOR adjacents = NULL;
    int h, v;
    NODE tempnode;
    if (!Locate(node, &h, &v, zero))     return adjacents;
    if (h == 0 && v == 0)                                       //空格位置
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h + 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 0 && v == 1)                                  //空格位置
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h, v - 1);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 0 && v == 2)                                  //空格位置
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h, v - 1);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 1 && v == 0)                                  //空格位置
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 1 && v == 1)                                  //空格位置
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v - 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 1 && v == 2)
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v - 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 2 && v == 0)
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 2 && v == 1)
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v - 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 2 && v == 2)
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v - 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    return adjacents;
}

//3.10 非连通性证明
void Prove(NODE start, NODE end, int target)   //判断节点是否在图中，并获取路径
{
    NODE node;
    NEIGHBOR* alladjacents = (NEIGHBOR*)malloc(sizeof(NEIGHBOR));
    *alladjacents = NULL;
    NEIGHBOR adjacents = NULL, nowadjacents;
    Set(node, start);
    adjacents = ExpandNodes(node, target);
    *alladjacents = UnionAdjacents(adjacents, *alladjacents);
    nowadjacents = *alladjacents;
    while (nowadjacents)
    {
        Set(node, nowadjacents->node);
        adjacents = ExpandNodes(node, target);
        adjacents = DiffAdjancents(adjacents, *alladjacents);
        *alladjacents = UnionAdjacents(adjacents, *alladjacents);
        printf("Now Counter:%.0lf\n", count);                    //用来显示当前node展开后的count值
        ClearNeighbors(adjacents);
        nowadjacents = nowadjacents->next;
    }
}

//3.10.M 主程序
int main()
{
    NODE start = { {1,2,3},{8,4,0},{7,6,5} }, end = { {1,2,3},{8,0,4},{7,6,5} };
    printf("Prove from:\n");
    PriNode(start);
    printf("to:\n");
    PriNode(end);
    Prove(start, end, ZERO);
    printf("\nCounter=%.0lf\n", count);
    printf("=============\n");
}